package binarytree;


import java.util.*;

public class BinaryTree {
    public static class TreeNode {
        public char val;
        public int res;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
        public TreeNode(int res) {
            this.res = res;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        TreeNode root = A;
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return root;
    }
    public TreeNode createTree01() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');


        TreeNode root = A;
        A.left = B;
        A.right = C;
        B.left = D;
        C.right = F;
        C.left = G;
        D.left = E;
        F.right = H;
        return root;
    }
    // 前序遍历
    void preOrder(TreeNode root) {
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");

        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root) {
        if(root==null) {
            return;
        }

        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root) {
        if(root==null) {
            return;
        }

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");

    }

    public int nodeSize;
    // 获取树中节点的个数
    int size(TreeNode root) {
        if(root==null) {
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    /*int size(TreeNode root) {
        sizeNode(root);
        return nodeSize;
    }
    void sizeNode(TreeNode root) {
        if(root==null) {
            return;
        }
        nodeSize++;
        int sizeLeft = size(root.left);
        int sizeRight = size(root.right);
    }*/
    // 获取叶子节点的个数
    public int leafNode;
    int getLeafNodeCount(TreeNode root) {
        if(root==null) {
            return 0;
        }
        if((root.left==null)&&(root.right==null)){
            return 1;
        }
        return  getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
    }
/*    int getLeafNodeCount(TreeNode root) {
        if(root==null) {
            return 0;
        }
        if((getLeafNodeCount(root.left)==0)&(getLeafNodeCount(root.right)==0)) {
            leafNode++;
        }
        return leafNode;
    }*/
    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k) {
        if(root==null) {
            return 0;
        }
        if(k==1) {
            return 1;
        }

        return getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if(root==null) {
            return 0;
        }

        return 1+(Math.max(getHeight(root.left), getHeight(root.right)));
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if(root==null) {
            return null;
        }
        if(root.val==val) {
            return root;
        }
        if(find(root.left,val)!=null) {
            return find(root.left,val);
        };
        if(find(root.right,val)!=null) {
            return find(root.right,val);
        };
        return null;
    }
    //层序遍历
    public Queue<TreeNode> queue = new LinkedList<>();

    void levelOrder01(TreeNode root) {
        if(root==null) {
            return;
        }
        queue.offer(root);
        levelOrderQueue(root);
    }
    void levelOrderQueue(TreeNode root) {
        if(root==null) {
            return;
        }
        if(root.left!=null) {
            queue.offer(root.left);
        }
        if(root.right!=null) {
            queue.offer(root.right);
        }
        System.out.print(queue.poll().val+" ");
        levelOrderQueue(queue.peek());
    }
    void subtreeOrder(TreeNode left,TreeNode right) {
        if(left==null&&right==null) {
            return;
        }
        if(left!=null&&right==null) {
            System.out.print(left.val+" ");
            subtreeOrder(left.left,left.right);
        } else if(right!=null&&left==null) {
            System.out.print(right.val+" ");
            subtreeOrder(right.left,right.right);
        } else {
            System.out.print(left.val+" ");
            System.out.print(right.val+" ");
        }
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if(root==null) {
            return true;
        }
        Queue<TreeNode> queue01 = new LinkedList<>();
        queue01.offer(root);

        while(queue01.peek()!=null) {
            TreeNode tmpNode = queue01.poll();
            queue01.offer(tmpNode.left);
            queue01.offer(tmpNode.right);
        }
        int size = queue01.size();
        for (int i = 0; i < size; i++) {
            if(queue01.poll()!=null) {
                return false;
            }
        }
        return true;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p!=null&&q==null) {
            return false;
        }
        if(p==null&&q!=null) {
            return false;
        }
        if(p==null||q==null) {
            return true;
        }
        if(p.val!=q.val) {
            return false;
        }
        if(isSameTree(p.left,q.left)==false) {
            return false;
        }
        if(isSameTree(p.right,q.right)==false) {
            return false;
        }
        return true;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null) {
            return false;
        }
        if(root.val==subRoot.val&&isSameTree(root,subRoot)) {
            return true;
        }
        isSameTree(root.left,subRoot);
        isSameTree(root.right,subRoot);
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if(root==null) {
            return root;
        }
        if(root.left!=null&&root.right==null) {
            root.right = root.left;
            root.left = null;
            return root;
        }
        if(root.right!=null&&root.left==null) {
            root.left = root.right;
            root.right = null;
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public int Difference(TreeNode left,TreeNode right) {
        if(Math.abs(Depth(left)-Depth(right))<=1) {
            return Math.abs(Depth(left)-Depth(right));
        } else {
            return -1;
        }
    }
        public int Depth(TreeNode node) {
            if(node==null) {
                return 0;
            }
            int left = Depth(node.left);
            if(left<0) {
                return -1;
            }
            int right = Depth(node.right);
            if(left>=0&&right>=0&&Math.abs(left-right)<=1) {
                return 1 + ((left>right)?left:right);
            } else {
                return -1;
            }

        }
    public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        if(Difference(root.left,root.right)>=2) {
            return false;
        }
        if(!isBalanced(root.left)) {
            return false;
        }
        if(!isBalanced(root.right)) {
            return false;
        }
        return true;
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null) {
            return true;
        }
        return isSameTwoNode(root.left,root.right);
    }
    public boolean isSameTwoNode(TreeNode left,TreeNode right) {
        if((left==null&&right!=null)||(left!=null&&right==null)) {
            return false;
        }
        if(left.val!=right.val) {
            return false;
        }
        return isSameTwoNode(left.left,right.right)
                &&isSameTwoNode(left.right,right.left);
    }
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public Stack<TreeNode> getStack(TreeNode root, TreeNode t) {
        Stack<TreeNode> stack = new Stack<>();
        if(root==null) {
            return stack;
        }
        inStack(root,t,stack);
        return stack;
    }
    public TreeNode inStack(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
              return null;
        }
        stack.push(root);
        if(root==node) {
            return root;
        }

        if(inStack(root.left, node, stack)==null
                &&inStack(root.right, node, stack)==null) {
            stack.pop();
            return null;
        } else {
            return root;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> pstack = getStack(root,p);
        Stack<TreeNode> qstack = getStack(root,q);
        Stack<TreeNode> max;
        Stack<TreeNode> min;
        if(pstack.size()>qstack.size()) {
            max = pstack;
            min = qstack;
        } else {
            max = qstack;
            min = pstack;
        }
        while (max.size()!=min.size()) {
            max.pop();
        }
        while (max.peek()!=min.peek()) {
            max.pop();
            min.pop();
        }
        return max.peek();
    }

    public int index(int[] arr, int val) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==val) {
                return i;
            }
        }
        return -1;
    }
    public int count;
    public int begin;
    class Solution {
        public int preindex = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return inbuildTree(preorder,inorder,0,inorder.length-1);
        }
        public int findIndex(int[] inorder,int begin,int end,int x) {
            for(int i = begin;i <= end;i++) {
                if(inorder[i]==x) {
                    return i;
                }
            }
            return -1;
        }
        public TreeNode inbuildTree(int[] preorder,int[] inorder,int begin,int end) {
            if(begin>end) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[preindex]);
            int index = findIndex(inorder,begin,end,preorder[preindex]);
            if(index==-1) {
                return null;
            }
            preindex++;
            root.left = inbuildTree(preorder,inorder,begin,index-1);
            root.right = inbuildTree(preorder,inorder,index+1,end);
            return root;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        class Node{
            public int postcount = postorder.length-1;
            public TreeNode inbuildTree(int[] inorder, int[] postorder,int begin,int end) {
                if(begin>end) {
                    return null;
                }
                TreeNode root = new TreeNode(postorder[postcount]);
                int index = findIndex(inorder,postorder[postcount],begin,end);
                if(index==-1) {
                    return null;
                }
                postcount--;
                root.right = inbuildTree(inorder,postorder,index+1,end);
                root.left = inbuildTree(inorder,postorder,begin,index-1);
                return root;
            }
            public int findIndex(int[] inorder, int x, int begin, int end) {
                for (int i = begin; i <= end; i++) {
                    if(inorder[i]==x) {
                        return i;
                    }
                }
                return -1;
            }
        }
        Node node = new Node();
        return node.inbuildTree(inorder,postorder,0,postorder.length-1);
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null) {
            stack.push(root);
            list.add(root.res);
            root = root.left;
        }
        while (stack.size()!=0) {
            TreeNode tmp = stack.pop();
            while (tmp!=null) {
                list.add(tmp.res);
                tmp = tmp.right;
            }
        }
        return list;
    }
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty()||cur!=null) {
            while(cur!=null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            list.add(tmp.val);
            cur = tmp.right;
        }
        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            TreeNode cur = root;

            while(cur!=null||!stack.isEmpty()) {
                while (cur!=null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.peek();
                TreeNode prev = null;
                if(top.right==null&&top.right==prev) {
                    list.add(top.res);
                    stack.pop();
                    prev = top;
                }else {
                    cur = top.right;
                }
            }
            return list;
    }

}
/*public StringBuilder str = new StringBuilder();
public String tree2str(TreeNode root) {
    StringBuilder s = solveString(root);
    return s.toString();
}
public StringBuilder solveString(TreeNode root) {
    if(root==null) {
        return str;
    }
    str.append(root.val+"(");
    if(root.left!=null) {
        str.append("(");
        solveString(root.left);
        str.append(")");
    }else {
        if(root.right==null) {
            return str;
        } else {
            str.append("()");
            return str;
        }
    }
    if(root.right==null) {
        return str;
    }else {
        str.append("(");
        solveString(root.right);
        str.append(")");
    }

    return str;
}*/
class Solution {
        /*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null) {
                return null;
            }
            if(root==p||root==q) {
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(left==null&&right!=null) {
                return right;
            }
            if(left!=null&&right==null) {
                return left;
            }
            if(left!=null&&right!=null) {
                return root;
            }
            return null;
        }*/

}
/*    class Solution {
        List<Integer> list;

        public Solution() {
            this.list = new ArrayList<>();
        }

        public List<Integer> preorderTraversal(TreeNode root) {
            if(root==null) {
                return list;
            }
            list.add(root.res);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
            return list;
        }
    }*/